2023-08-05 CA CURVE

Ця курва

Тут покажемо як працює підпис ECDSA на рівні операцій над точкою, що знаходиться на еліптичній кривій, та операціями додавання та множення які рухать точку по цій кривій.

Точка на лінії

Для початку визнається точка на площині в координатах Якобі.


defmodule CA.Point do
  defstruct [:x, :y, z: 0]
  def isAtInfinity?(p) do
    p.y == 0
  end

end

Та функція визначення належності точки до геометричного місця точок кривої (локуса).


defmodule CA.Curve do
  @moduledoc false
  require CA.Integer
  require CA.Point
  defstruct [:A, :B, :P, :N, :G, :name, :oid]
  def contains?(curve, p) do
      cond do
        p.x < 0 || p.x > curve."P" - 1 -> false
        p.y < 0 || p.y > curve."P" - 1 -> false
        CA.Integer.ipow(p.y, 2) - (CA.Integer.ipow(p.x, 3)
                                + curve."A" * p.x + curve."B")
          |> CA.Integer.modulo(curve."P") != 0 -> false
        true -> true
      end
  end
  def getLength(curve) do
      div(1 + String.length(Integer.to_string(curve."N", 16)), 2)
  end
end

Множення в координатах Якобі

Алгоритм бінарного множення в координатах Якобі.


defmodule CA.Jacobian do
  require CA.Integer
  require CA.Point
  @moduledoc false

  def toJacobian(p), do: %CA.Point{x: p.x, y: p.y, z: 1}
  def fromJacobian(p, cP) do
      z = inv(p.z, cP)
      %CA.Point{
        x: CA.Integer.modulo(p.x * CA.Integer.ipow(z, 2), cP),
        y: CA.Integer.modulo(p.y * CA.Integer.ipow(z, 3), cP)
      }
  end

  def multiply(p, n, cN, cA, cP), do:
      p |> toJacobian()
        |> jacobianMultiply(n, cN, cA, cP)
        |> fromJacobian(cP)
  def add(p, q, cA, cP), do:
      jacobianAdd(toJacobian(p), toJacobian(q), cA, cP)
        |> fromJacobian(cP)
  def inv(x, _) when x == 0, do: 0
  def inv(x, n), do:
      invOperator(1, 0, CA.Integer.modulo(x, n), n)
        |> CA.Integer.modulo(n)
  def invOperator(lm, hm, low, high) when low > 1 do
      r = div(high, low)
      invOperator(hm - lm * r, lm, high - low * r, low) end
  def invOperator(lm, _, _, _), do: lm

  def jacobianDouble(p, cA, cP) do
      if p.y == 0 do
         %CA.Point{x: 0, y: 0, z: 0}
      else
        ysq = CA.Integer.ipow(p.y, 2) |> CA.Integer.modulo(cP)
        s = (4 * p.x * ysq) |> CA.Integer.modulo(cP)
        m = (3 * CA.Integer.ipow(p.x, 2) + cA * CA.Integer.ipow(p.z, 4))
          |> CA.Integer.modulo(cP)
        nx = (CA.Integer.ipow(m, 2) - 2 * s) |> CA.Integer.modulo(cP)
        ny = (m * (s - nx) - 8 * CA.Integer.ipow(ysq, 2))
          |> CA.Integer.modulo(cP)
        nz = (2 * p.y * p.z) |> CA.Integer.modulo(cP)
        %CA.Point{x: nx, y: ny, z: nz}
      end
  end

  def jacobianAdd(p, q, cA, cP) do
      if p.y == 0 do
         q
      else
         if q.y == 0 do
            p
         else
           u1 = (p.x * CA.Integer.ipow(q.z, 2)) |> CA.Integer.modulo(cP)
           u2 = (q.x * CA.Integer.ipow(p.z, 2)) |> CA.Integer.modulo(cP)
           s1 = (p.y * CA.Integer.ipow(q.z, 3)) |> CA.Integer.modulo(cP)
           s2 = (q.y * CA.Integer.ipow(p.z, 3)) |> CA.Integer.modulo(cP)

           if u1 == u2 do
             if s1 != s2 do
                %CA.Point{x: 0, y: 0, z: 1}
             else
               jacobianDouble(p, cA, cP)
             end
           else
             h = u2 - u1
             r = s2 - s1
             h2 = (h * h) |> CA.Integer.modulo(cP)
             h3 = (h * h2) |> CA.Integer.modulo(cP)
             u1h2 = (u1 * h2) |> CA.Integer.modulo(cP)
             nx = (CA.Integer.ipow(r, 2) - h3 - 2 * u1h2) |> CA.Integer.modulo(cP)
             ny = (r * (u1h2 - nx) - s1 * h3) |> CA.Integer.modulo(cP)
             nz = (h * p.z * q.z) |> CA.Integer.modulo(cP)
             %CA.Point{x: nx, y: ny, z: nz}
           end
         end
       end
  end

  def jacobianMultiply(_p, n, _cN, _cA, _cP) when n == 0, do:
      %CA.Point{x: 0, y: 0, z: 1}
  def jacobianMultiply(p, n, _cN, _cA, _cP) when n == 1 do
      case p.y do
           0 -> %CA.Point{x: 0, y: 0, z: 1}
           _ -> p
      end
  end
  def jacobianMultiply(p, n, cN, cA, cP) when n < 0 or n >= cN do
      case p.y do
           0 -> %CA.Point{x: 0, y: 0, z: 1}
           _ -> jacobianMultiply(p, CA.Integer.modulo(n, cN), cN, cA, cP)
      end
  end
  def jacobianMultiply(p, _n, _cN, _cA, _cP) when p.y == 0, do:
      %CA.Point{x: 0, y: 0, z: 1}
  def jacobianMultiply(p, n, cN, cA, cP) when rem(n, 2) == 0 do
      jacobianMultiply(p, div(n, 2), cN, cA, cP) |> jacobianDouble(cA, cP)
  end
  def jacobianMultiply(p, n, cN, cA, cP) do
      jacobianMultiply(p, div(n, 2), cN, cA, cP)
      |> jacobianDouble(cA, cP) |> jacobianAdd(p, cA, cP)
  end

end

Множення в координатах Якобі

Параметри кривих ідентифікуються атомом та/або OID, та визначають точки А, Б, Засіювання, Точка на кривій, Порядок, Кофактор.


defmodule CA.KnownCurves do
  require CA.Curve
  require CA.Point

  @secp256k1Oid {1, 3, 132, 0, 10}
  @secp256k1name :secp256k1
  @prime256v1 {1, 2, 840, 10045, 3, 1, 7}
  @prime256v1name :prime256v1

  def getCurveByOid(oid) do
    case oid do
      @secp256k1Oid -> secp256k1()
      @prime256v1 -> prime256v1()
    end
  end

  def getCurveByName(name) do
    case name do
      @secp256k1name -> secp256k1()
      @prime256v1name -> prime256v1()
    end
  end

  def secp256k1() do
    %CA.Curve{
      name: @secp256k1name,
      A: 0x0000000000000000000000000000000000000000000000000000000000000000,
      B: 0x0000000000000000000000000000000000000000000000000000000000000007,
      P: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,
      N: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
      G: %CA.Point{
        x: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
        y: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
      },
      oid: @secp256k1Oid
    }
  end

  def prime256v1() do
    %CA.Curve{
      name: @prime256v1name,
      A: 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC,
      B: 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B,
      P: 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF,
      N: 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551,
      G: %CA.Point{
        x: 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
        y: 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
      },
      oid: @prime256v1
    }
  end
end

BigNum RND

Алгоритм генерація великого довільного числа, яке береться як координата точки на еліптичній кривій, автоматично визначається її пара, яка утворює точку на прямій, і далі відбуваються подальші криптографічні перетворення.


defmodule CA.Integer do
  @moduledoc false
  import Bitwise

  def modulo(x, n), do: rem(x, n) |> correctNegativeModulo(n)
  def correctNegativeModulo(r, n) when r < 0, do: r + n
  def correctNegativeModulo(r, _n), do: r
  def ipow(base, p, acc \\ 1)
  def ipow(base, p, acc) when p > 0, do: ipow(base, p - 1, base * acc)
  def ipow(_base, _p, acc), do: acc

  def between(minimum, maximum) when minimum < maximum do
      range = maximum - minimum + 1
      {bytesNeeded, mask} = calculateParameters(range)
      randomNumber = :crypto.strong_rand_bytes(bytesNeeded)
                  |> :binary.bin_to_list()
                  |> bytesToNumber &&& mask

      if randomNumber < range do
         minimum + randomNumber
      else
         between(minimum, maximum)
      end
  end

  def bytesToNumber(randomBytes, randomNumber \\ 0, i \\ 0)
  def bytesToNumber([randomByte | otherRandomBytes], randomNumber, i), do:
      bytesToNumber(otherRandomBytes, randomNumber ||| randomByte <<< (8 * i), i + 1)
  def bytesToNumber([], randomNumber, _i), do: randomNumber

  def calculateParameters(range), do: calculateParameters(range, 1, 0)
  def calculateParameters(range, mask, bitsNeeded) when range > 0, do:
      calculateParameters(range >>> 1, mask <<< 1 ||| 1, bitsNeeded + 1)
  def calculateParameters(_range, mask, bitsNeeded), do:
      {div(bitsNeeded, 8) + 1, mask}

end

ECDSA

Обчислення r та s для криптографічного підпису.


defmodule CA.ECDSA do
  require CA.Point
  require CA.Integer
  require CA.Jacobian
  require CA.ECDSA.OTP

  def numberFromString(data) do
      Base.encode16(data)
      |> Integer.parse(16)
      |> (fn {parsedInt, ""} -> parsedInt end).()
  end

  def sign(message, privateKey, options \\ []) do
      %{hashfunc: hashfunc} = Enum.into(options, %{hashfunc: :sha256})
      number = :crypto.hash(hashfunc, message) |> numberFromString()
      curve = CA.KnownCurves.secp256k1()
      randNum = CA.Integer.between(1, curve."N" - 1)
      r = CA.Jacobian.multiply(curve."G", randNum, curve."N", curve."A", curve."P").x
        |> CA.Integer.modulo(curve."N")
      s = ((number + r * privateKey) * CA.Jacobian.inv(randNum, curve."N"))
        |> CA.Integer.modulo(curve."N")
      {r, s}
  end

  def private(bin), do: :erlang.element(2,X509.PrivateKey.from_pem(bin))
  def public(bin),  do: :public_key.pem_entry_decode(hd(:public_key.pem_decode(bin)))

  def verify(file, signature, pub) do
      {:ok, msg} = :file.read_file file
      {:ok, pem} = :file.read_file pub
      verify(msg, CA.ECDSA.OTP.signature(signature), public(pem), [])
  end

  def verify(message, {r,s}, publicKey, options) do
      %{hashfunc: hashfunc} = Enum.into(options, %{hashfunc: :sha256})
      number = :crypto.hash(hashfunc, message) |> numberFromString()
      curve = CA.KnownCurves.secp256k1()
      inv = CA.Jacobian.inv(s, curve."N")
      v = CA.Jacobian.add(
        CA.Jacobian.multiply(curve."G", CA.Integer.modulo(number * inv, curve."N"),
           curve."N", curve."A", curve."P"),
        CA.Jacobian.multiply(publicKey, CA.Integer.modulo(r * inv, curve."N"),
           curve."N", curve."A", curve."P" ), curve."A", curve."P")
      cond do
        r < 1 || r >= curve."N" -> false
        s < 1 || s >= curve."N" -> false
        CA.Point.isAtInfinity?(v) -> false
        CA.Integer.modulo(v.x, curve."N") != r -> false
        true -> true
      end
  end

end

Висновки

Промислової якості криптографічні перетворення з використанням бібліотеки великих цілих чисел GMP вбудованої в віртуальну машину Erlang вміщаються в 250 LOC та всього в декілька разів повільніше OpenSSL імплементації на мові C.

OpenSSL ECC Sign/Verify

> CA.CSR.ca
> CA.CSR.csr "m2"
> CA.CSR.client "m2"

# export client=m2
# openssl dgst -sha256 -sign $client.key mix.exs > mix.sig

# export client=m2
# openssl dgst -sha256 -verify $client.pub -signature mix.sig mix.exs